package com.cube.algorithms.heuristic;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author litb
 * @since 2025/6/18 19:52
 * <p>
 * 使用禁忌搜索 (Tabu Search) 算法解决旅行商问题 (TSP) 的示例。
 */

public class TspTabuSearchExample {

    // --- 1. 基础数据结构 ---

    // --- 3. 主程序入口 ---
    public static void main(String[] args) {
        // 创建城市仓库
        List<City> cities = new ArrayList<>();
        cities.add(new City("北京", 116.46, 39.92));
        cities.add(new City("上海", 121.48, 31.22));
        cities.add(new City("广州", 113.23, 23.16));
        cities.add(new City("深圳", 114.07, 22.62));
        cities.add(new City("成都", 104.06, 30.67));
        cities.add(new City("杭州", 120.19, 30.26));
        cities.add(new City("西安", 108.95, 34.27));
        cities.add(new City("武汉", 114.31, 30.52));


        // 创建算法实例并执行
        TspTabuSearchExample solver = new TspTabuSearchExample();
        // 设置禁忌搜索参数：禁忌长度，最大迭代次数
        Tour resultTour = solver.findTour(cities, 20, 1000);

        // 打印最终结果
        System.out.println("禁忌搜索算法找到的路径:");
        String pathString = resultTour.getTour().stream()
                .map(City::getName)
                .collect(Collectors.joining(" -> "));
        System.out.println(pathString + " -> " + resultTour.getCity(0).getName());
        System.out.printf("总距离: %.2f%n", resultTour.getTotalDistance());
    }

    /**
     * 禁忌搜索主算法。
     *
     * @param cities        城市列表
     * @param tabuTenure    禁忌长度（一个移动被禁止的迭代次数）
     * @param maxIterations 最大迭代次数
     * @return 找到的最优路径
     */
    public Tour findTour(List<City> cities, int tabuTenure, int maxIterations) {
        // 1. 生成初始解
        Tour bestSolution = new Tour(cities);
        // 从一个随机解开始
        Collections.shuffle(bestSolution.tour);
        Tour currentSolution = bestSolution;

        // 2. 初始化禁忌列表 (使用LinkedList作为队列)
        LinkedList<SwapMove> tabuList = new LinkedList<>();

        for (int iter = 0; iter < maxIterations; iter++) {
            Tour bestNeighbor = null;
            SwapMove bestMove = null;
            double bestNeighborCost = Double.MAX_VALUE;

            // 3. 探索当前解的邻域
            // 邻域定义为：通过一次两两交换产生的所有解
            for (int i = 0; i < currentSolution.tourSize(); i++) {
                for (int j = i + 1; j < currentSolution.tourSize(); j++) {
                    SwapMove currentMove = new SwapMove(i, j);
                    Tour neighbor = currentSolution.swap(i, j);
                    double neighborCost = neighbor.getTotalDistance();

                    // 4. 检查移动是否被禁忌
                    if (!tabuList.contains(currentMove)) {
                        // 如果未被禁忌，且是当前邻域中最好的，则记录下来
                        if (neighborCost < bestNeighborCost) {
                            bestNeighbor = neighbor;
                            bestMove = currentMove;
                            bestNeighborCost = neighborCost;
                        }
                    } else {
                        // 5. 渴望准则：如果移动被禁忌，但能产生一个历史最优解，则"特赦"
                        if (neighborCost < bestSolution.getTotalDistance()) {
                            bestNeighbor = neighbor;
                            bestMove = currentMove;
                            bestNeighborCost = neighborCost;
                        }
                    }
                }
            }

            // 如果找到了一个可行的移动
            if (bestNeighbor != null) {
                // 6. 移动到邻域中的最优解（即使它比当前解差）
                currentSolution = bestNeighbor;

                // 7. 更新禁忌列表
                tabuList.addLast(bestMove);
                if (tabuList.size() > tabuTenure) {
                    tabuList.removeFirst(); // 维持禁忌列表的固定长度
                }

                // 8. 如果新解优于历史最优解，则更新历史最优解
                if (bestNeighborCost < bestSolution.getTotalDistance()) {
                    bestSolution = bestNeighbor;
                }
            }
        }

        return bestSolution;
    }

    /**
     * 城市类，表示地图上的一个点。
     */
    public static class City {
        private final String name;
        private final double x;
        private final double y;

        public City(String name, double x, double y) {
            this.name = name;
            this.x = x;
            this.y = y;
        }

        public String getName() {
            return name;
        }

        public double distanceTo(City other) {
            // ... (distance calculation logic)
            double deltaX = this.x - other.x;
            double deltaY = this.y - other.y;
            return Math.sqrt(deltaX * deltaX + deltaY * deltaY);
        }

        @Override
        public String toString() {
            return getName();
        }
    }


    // --- 2. 核心禁忌搜索算法 ---

    /**
     * 路径类，代表一个TSP问题的解。
     */
    public static class Tour {
        private final List<City> tour;

        public Tour(List<City> cities) {
            this.tour = new ArrayList<>(cities);
        }

        public double getTotalDistance() {
            double totalDistance = 0;
            for (int i = 0; i < tour.size() - 1; i++) {
                totalDistance += tour.get(i).distanceTo(tour.get(i + 1));
            }
            if (!tour.isEmpty()) {
                totalDistance += tour.get(tour.size() - 1).distanceTo(tour.get(0));
            }
            return totalDistance;
        }

        public int tourSize() {
            return tour.size();
        }

        public City getCity(int index) {
            return tour.get(index);
        }

        public List<City> getTour() {
            return Collections.unmodifiableList(tour);
        }

        /**
         * 创建一个应用了2-opt交换的新路径。
         *
         * @param i 第一个交换点
         * @param k 第二个交换点
         * @return 一个新的Tour对象
         */
        public Tour swap(int i, int k) {
            List<City> newTour = new ArrayList<>(this.tour);
            Collections.swap(newTour, i, k);
            return new Tour(newTour);
        }
    }

    /**
     * 定义一个"移动"，即交换两个城市的位置。
     * 用于放入禁忌列表。
     */
    public static class SwapMove {
        private final int index1;
        private final int index2;

        public SwapMove(int index1, int index2) {
            // 保证顺序一致，便于比较
            this.index1 = Math.min(index1, index2);
            this.index2 = Math.max(index1, index2);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            SwapMove swapMove = (SwapMove) o;
            return index1 == swapMove.index1 && index2 == swapMove.index2;
        }

        @Override
        public int hashCode() {
            return Objects.hash(index1, index2);
        }
    }
} 